There are two major classes of quantization algorithms, namely: scalar quantizers (SQs), which process an input vector element by element, and vector quantizers (VQs), which quantize an input vector as one unit (all vector dimensions are quantized jointly). At a given bitrate, VQs are superior to the SQs, but at a cost of increased computational complexity and memory storage.
Let the target vector to quantize be M dimensional: s=[s(1) s(2) . . . s(M)]. The VQ algorithm performs a search in a codebook (CB) of size K, {ck}k=1K of pre-stored M dimensional codevectors ck=[ck(1) ck(2) . . . ck(M)]. Such a search returns the index of the codebook vector that provides the best match kopt based on a distortion measure d(s,ck). Equations (1-2) below describe this operation, assuming that the search criterion is based on a squared error:
                              k          opt                =                              argmin            k                    ⁢                      d            ⁡                          (                              s                ,                                  c                  k                                            )                                                          (        1        )                                          d          ⁡                      (                          s              ,                              c                k                                      )                          =                              ∑                          m              =              1                        M                    ⁢                                    (                                                s                  ⁡                                      (                    m                    )                                                  -                                                      c                    k                                    ⁡                                      (                    m                    )                                                              )                        2                                              (        2        )            
The optimal index kopt is transmitted to the decoder, and the corresponding codevector is extracted from the CB (identical CBs are available both at the encoder and the decoder) and is used to reconstruct the target vector. The CB is typically trained offline and captures the statistical properties of the data. In many cases the simple squared error (cf. equation (2)) is modified with weights, such that:
                              d          ⁡                      (                          s              ,                              c                k                                      )                          =                              ∑                          m              =              1                        M                    ⁢                                    w              ⁡                              (                m                )                                      ·                                          (                                                      s                    ⁡                                          (                      m                      )                                                        -                                                            c                      k                                        ⁡                                          (                      m                      )                                                                      )                            2                                                          (        3        )            where the weights w(m) are application dependent. For simplicity of the presentation herein, only squared error, defined in equation (2) will be used in the further description. However, it should be noted that the principles discussed herein are valid also when more sophisticated criteria, such as the one in equation (3), are used.
As may be concluded from the description above, the accuracy or quality of the reconstructed target signal is dependent on the size K of the codebook; where a large CB leads to higher accuracy, and thus better quality, than a smaller CB. At the same time, from equation (1) it may be concluded that the main computational complexity also is related to the size of the CB, assuming that the vector dimensionality is fixed by the application.
Typically, audio transmission systems are built under the constraints of limited computational complexity. That is, the worst case complexity should not exceed a certain pre-defined level LMAX. For example, the computational complexity of an audio codec is typically measured by means of Weighted Millions of Operations per Second (WMOPS), but as we consider a VQ module, the complexity is directly related to the size of the search space (size of the CB). A VQ is typically the most complex module in a codec, and further, the CB search (number of comparisons with CB vectors) is what makes the VQ so complex.
If a VQ system is to quantize one target vector s at a time, the search space K has to be optimized such that complexity does not exceed LMAX. Some off-line optimization techniques, such as split and multi-stage VQ can provide certain reduction of complexity (and storage), given the properties of vector s and the quality requirements for the reconstructed vector.
If the VQ system is to quantize multiple target (input) vectors {sn}n=1N at a time, with a varying number of vectors N, the off-line optimization techniques mentioned above are not capable of maintaining complexity and quality constraints. In such cases, the offline optimization have to find a balance between contradicting requirements of A) limiting complexity (=limiting the search) when a large number of input vectors are to be quantized simultaneously, and B) maintaining high accuracy (=search in large codebook) when a low number of vectors are to be quantized, which is not a simple task.